package com.tgy.topk;

import com.common.sort.tools.Integers;

/**
 * @Author: tgy
 * @Date: 2020-10-16 14:59
 */
public class TopKQuickSort<E> {

    private E[] elements;

    private int cmpCount;

    private int k;

    public void topK(E[] elements, int k) {

        this.elements = elements;
        this.k = elements.length - k;

        topK(0,elements.length);

//        Integers.println((Integer[]) elements,elements.length - k, elements.length);
    }

    public void topK(int begin, int end) {


        if (end - begin < 2) {

            return;
        }

        int left = begin,right = end - 1;


        E e = elements[left];

        while (left < right) {

            while (left < right) {

                if (cmp(e,elements[right]) < 0) {

                    right--;
                }else {

                    elements[left++] = elements[right];
                    break;
                }
            }

            while (left < right) {

                if (cmp(e,elements[left]) > 0) {

                    left++;
                }else {

                    elements[right--] = elements[left];
                    break;
                }

            }
        }

        elements[left] = e;


        if (left > k - 1) {

            topK(begin,left);
            topK(left + 1,end);
        }else if (left < k - 1) {

            topK(left + 1,end);
        }else {

            return;
        }

    }

    private int cmp(E e1, E e2) {

        cmpCount++;
        return  ((Comparable)e1).compareTo(e2);
    }

    @Override
    public String toString() {
        return "比较次数:" + cmpCount;
    }
}
